/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/water-and-jug-problem
   @Language: C++
   @Datetime: 19-05-28 15:57
   */

// Method 1, simulate, Time 10ms
class Solution {
public:
	/**
	 * @param x: the given number x
	 * @param y: the given number y
	 * @param z: the given number z
	 * @return: whether it is possible to measure exactly z litres using these two jugs
	 * Tip:
	 * water-n*x=z, --> water-z=n*x, --> (water-z)%x==0
	 * remain=water%x, water=y-(x-remain)
	 */
	bool canMeasureWater(int x, int y, int z) {
		// Write your code here
		if(x>y) return canMeasureWater(y,x,z);
		for(int w=y, r=w%x; r; r=w%x){
			if((w-z)%x==0) return true;
			w=y-(x-r);
		}
		return false;
	}
};

// Method 2, gcd, Time 6ms
class Solution {
public:
	/**
	 * @param x: the given number x
	 * @param y: the given number y
	 * @param z: the given number z
	 * @return: whether it is possible to measure exactly z litres using these two jugs
	 * Tip:
	 * z=m*x+n*y, positive: get water; negtive: drop water
	 * z=m*x+n*y, --> z=gcd(x,y)*k, z%(gcd(x,y))==0
	 */
	bool canMeasureWater(int x, int y, int z) {
		// Write your code here
		return x+y>=z && z%__gcd(x,y)==0;
	}
};
